\documentclass{article}
\usepackage{amsfonts, amsmath, amsthm, amssymb, array, color, enumitem}
\usepackage[normalem]{ulem}
\usepackage{tikz} 
\usepackage[margin=1in]{geometry}

\usetikzlibrary{cd, arrows}

\renewcommand{\baselinestretch}{1.5}

\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\C}{\mathbb{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\B}{\mathcal{B}}
\newcommand{\CC}{\mathcal{C}}

\newcommand{\rightarrowdot}{\xrightarrow{\cdot}}
\newcommand{\e}{\varepsilon}

\DeclareMathOperator{\rank}{rank}
\DeclareMathOperator{\ob}{Obj}
\DeclareMathOperator{\arr}{Arr}
\DeclareMathOperator{\Hom}{Hom}
\DeclareMathOperator{\Lim}{Lim}
\DeclareMathOperator{\Colim}{Colim}

\newtheorem{thm}{Theorem}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{define}[thm]{Definition}
\newtheorem{ex}[thm]{Example}
\newtheorem{quest}[thm]{Question}

\renewcommand{\emph}{\textbf}

\definecolor{dgreen}{rgb}{0, .6, 0}
\definecolor{purple}{rgb}{.6, 0, .8}

\newcommand{\modStep}[1]{\textcolor{purple}{\underline{#1}}}


\begin{document}
{\center{\Large Accumulating Entropy with Adversarial Sources}}

Let
\begin{enumerate}
\item $D$ be a 2-monotone distribution with min-entroppy $k$.
\item $n \in \N$ be the length of sources $x_i$ for $0 \le i < N$ for some $N$.
\item $\pi: [n] \rightarrow [n]$ be a cyclic permutation ($\pi^m = id$ iff $n | m$).  Then $f_\pi: [2]^n \rightarrow [2]^n$ where $(x_0, \ldots, x_{n-1}) \mapsto (x_{\pi(0)}, \ldots, x_{\pi(n-1)}$.  Clearly, $f_\pi^m = f_{\pi^m}$.
\item $\A$ denote the adversary.
\item for any $0 \le p \le 1$, let $D_p$ be the distribution where 1 occurs with probability $p$ and 0 with probability $1-p$.
\item $p$ be the probability that $\A$ can replace a source with one of its choosing.

\end{enumerate}

\section{Version 1 (Sept 24, 2021)}

Hybrid $H_0$:
\begin{enumerate}
\item Let $R_0 = 0^n$.
\item For $0 \le i < N$,
	\begin{enumerate}
	\item Sample $x_i \leftarrow D$.
	\item $\A$ samples $b_i \leftarrow D_p$.  If $b_i = 1$, $\A$ chooses $y_i \in [2]^n$ and sets $x_i = y_i$.  Otherwise, $x_i$ is unaffected.
	\item $R_{i+1} = R_i \oplus f_\pi^i(x_i)$
	\end{enumerate}
\item $\A$ chooses and outputs $R_\A \in [2]^n$.
\item If $R_\A = R_N$, output 1.  Otherwise, output 0.  \textcolor{red}{modify for $R_\A \approx R_N$}
\end{enumerate}

Hybrid $H_1$: Same as $H_0$ except $\A$ chooses $R_\A$ before the experiment begins and always replaces $x_{N-1}$ with its choice $y_{N-1}$.

\begin{lem}
\[
P(H_0 = 1) \le P(H_1 = 1)
\]
\textcolor{red}{I think $P(H_1 = 1) = P(H_0 = 1)/(p + (1-p) P(\A \textnormal{ correctly guesses } x_{N-1})) \ge P(H_0 = 1)$.}
\end{lem}
\begin{proof}
Suppose $H_0 = 1$.  Then $\A$ predicted the value of $R_N$.  Let $R_\A$ be the string $\A$ choose before the experiment started.  Then choose $y_{N-1} = x_{N-1} \oplus R_N \oplus R_\A$.  Then
\[
R'_N := R_{N-1} \oplus y_{N-1} = R_{N-1} \oplus x_{N-1} \oplus R_N \oplus R_\A = R_N \oplus R_N \oplus R_\A = R_\A
\]
where $R'_N$ is the value of the register at the end of $H_1$.

\textcolor{red}{Suppose $H_1 = 1$.  If $\A$ in $H_0$ successfully replaces $x_{N-1}$ (which happens with probability $p$), then $H_0 = 1$ by an analogous argument to the one above.  If not, $\A$ must correctly guess $x_{N-1}$.  Since $(H_0 = 1) \implies (H_1 = 1)$, $(H_1 = 0) \implies (H_0 = 0)$, so $P(H_0 = 1) = (p + (1-p) P(\A \textnormal{ correctly guesses } x_{N-1})) P(H_1 = 1) \le P(H_1 = 1)$.}
\end{proof}

Hybrid $H_2$: Same as $H_1$ except $\A$ always chooses $R_\A = 0^n$.

\begin{lem}
\[
P(H_1 = 1) = P(H_2 = 1)
\]
\end{lem}
\begin{proof}
Suppose $H_1 = 1$.  Then $R_\A = R_N$.  If $\A$ replaced $x_{N-1}$ with $y_{N-1} \oplus R_\A$ instead of $y_{N-1}$, then $H_2 = 1$.  Thus $P(H_1 = 1) \le P(H_2 = 1)$.  The same argument proves $P(H_1 = 1) \ge P(H_2 = 1)$.
\end{proof}

\textcolor{red}{it is very easy (actually ``easier") in the proof of the first lemma to jump to $H_2$.  Is it worth having $H_1$?}

Hybrid $H_3$: Same as $H_2$ except $\A$ computes $T_0 = 0^n$ and $T_{i+1} = T_i \oplus f_\pi^i(y_i)$ if $b_i = 1$ and $T_{i+1} = T_i$ otherwise.

$\A$ only does computations on information it already knows, so it is equivalent to $H_2$.

Hybrid $H_4$: Same as $H_3$ except if $b_i = 1$, the choice of $y_i$ must satisfy $f_\pi^i(y_i) \& T_i = 0^n$.  

Alternate Hybrid $H'_3$: Same as $H_2$ except if $i < N-1$ and $b_i = 1$, $\A$ always chooses $y_i = 0$.  $\A$ can choose any string for $y_{N-1}$.

\textcolor{red}{I think this has the same effect as tagging, but is more streamlined.  This is Hybrid E?  I am not convinced this is trivially secure from No Time to Hash.  This behaves like having a sequence of permutations $\pi^{\ell_i}$ where $\ell_i$ are ``increasing" $\mod n$ instead of a constant permutation (which corresponds to the sequence $\pi^i$.  No Time to Hash does not give a description in that case.  We should be ok if for each $0 \le \ell < n$, $\exists 0 \le i < N$ such that $\ell_i = \ell$.  Seems stronger than we need, but would definitely work.  If $N$ is a multiple of $n$, ``increasing" corresponds to increasing as integers except at $N/n-1$ many $i$.}

\newpage


\section{Version 2 (Sept 28, 2021)}
Hybrid $H_0$:
\begin{enumerate}
\item Let $R_0 = 0^n$.
\item For $0 \le i < N$,
	\begin{enumerate}
	\item Sample $x_i \leftarrow D$.
	\item $\A$ samples $b_i \leftarrow D_p$.  If $b_i = 1$, $\A$ chooses $y_i \in \{0,1\}^n$ and sets $x_i = y_i$.  Otherwise, $x_i$ is unaffected.
	\item $R_{i+1} = R_i \oplus f_\pi^i(x_i)$
	\end{enumerate}
\item $\A$ chooses and outputs $R_\A \in \{0,1\}^n$.
\item If $R_\A = R_N$, output 1.  Otherwise, output 0.  \textcolor{red}{modify for $R_\A \approx R_N$}
\end{enumerate}

Hybrid $H_1$:
\begin{enumerate}\addtocounter{enumi}{-1}
\item \modStep{$\A$ chooses $R_\A$.}
\item Let $R_0 = 0^n$.
\item For $0 \le i < N$,
	\begin{enumerate}
	\item Sample $x_i \leftarrow D$.
	\item $\A$ samples $b_i \leftarrow D_p$.  If $b_i = 1$, $\A$ chooses $y_i \in \{0,1\}^n$ and sets $x_i = y_i$.  Otherwise, $x_i$ is unaffected.
	\item $R_{i+1} = R_i \oplus f_\pi^i(x_i)$
	\end{enumerate}
\item \modStep{$\A$ chooses $y_N \in \{0,1\}^n$ and outputs $R_\A$.  Compute $R_{N+1} = R_N \oplus y_N$.}
\item If \modStep{$R_\A = R_{N+1}$}, output 1.  Otherwise, output 0.
\end{enumerate}

\begin{lem}
\[
P(H_0 = 1) = P(H_1 = 1)
\]
\end{lem}
\begin{proof}
Suppose $H_0 = 1$.  Then $\A$ predicted the value of $R_N$.  Let $R_\A$ be the string $\A$ choose before the experiment started.  Then choose $y_N = \oplus R_N \oplus R_\A$.  Then $R_{N+1} := R_N \oplus y_N = R_\A$.

Suppose $H_1 = 1$.  Then $R_\A = R_N \oplus y_N$.  The adversary in $H_0$ would  know $R_\A$ and $y_N$, so they can $R_\A \oplus y_N$ at step 3.  Then $H_0 = 1$.
\end{proof}

Hybrid $H_2$:
\begin{enumerate}\addtocounter{enumi}{-1}
\item \textcolor{purple}{\sout{$\A$ chooses $R_\A$.}}
\item Let $R_0 = 0^n$.
\item For $0 \le i < N$,
	\begin{enumerate}
	\item Sample $x_i \leftarrow D$.
	\item $\A$ samples $b_i \leftarrow D_p$.  If $b_i = 1$, $\A$ chooses $y_i \in \{0,1\}^n$ and sets $x_i = y_i$.  Otherwise, $x_i$ is unaffected.
	\item $R_{i+1} = R_i \oplus f_\pi^i(x_i)$
	\end{enumerate}
\item $\A$ chooses $y_N \in \{ 0, 1 \}^n$ \textcolor{purple}{\sout{and outputs $R_\A$}}.  Compute $R_{N+1} = R_N \oplus y_N$.
\item If \modStep{$R_{N+1} = 0$}, output 1.  Otherwise, output 0.
\end{enumerate}

\begin{lem}
\[
P(H_1 = 1) = P(H_2 = 1)
\]
\end{lem}
\begin{proof}
Suppose $H_1 = 1$.  Then $R_\A = R_{N+1}$, so $\A$ knows $R_{N+1}$ and thus $R_N = R_{N+1} \oplus y_N$.  To succeed in $H_2$, $\A$ chooses $y_N = R_N$ instead.

Now suppose $H_2 = 1$.  Then $R_{N+1} = R_N \oplus y_N = 0$, so $\A$ was able to guess $y_N = R_N$.  Let $y_N = R_N \oplus R_\A$ instead.  Then $R_{N+1} = R_\A$.
\end{proof}

Hybrid $H_3$:
\begin{enumerate}
\item Let $R_0 = 0^n$ \modStep{and $E = 0$}.
\item For $0 \le i < N$,
	\begin{enumerate}
	\item Sample $x_i \leftarrow D$.
	\item $\A$ samples $b_i \leftarrow D_p$.  If $b_i = 1$, $\A$ chooses $y_i \in \{0,1\}^n$ and sets $x_i = y_i$.  \modStep{If $y_i \ne 0$, set $E = 1$.}  Otherwise, $x_i$ is unaffected.
	\item $R_{i+1} = R_i \oplus f_\pi^i(x_i)$
	\end{enumerate}
\item $\A$ chooses $y_N \in \{ 0, 1 \}^n$.  Compute $R_{N+1} = R_N \oplus y_N$.
\item If $R_{N+1} = 0$ \modStep{and $E = 0$}, output 1.  Otherwise, output 0.
\end{enumerate}

\begin{lem}
\[
P(H_2 = 1) = P(H_3 = 1)
\]
\end{lem}

\begin{proof}
Suppose $H_2 = 1$.  Since the $x_i$ are independent, they do not depend on $R_j$ for $j < 1$.  Thus if an $x_i$ is replaced with $y_i$, it does not influence the other $x_j$.  Suppose $\A$ in $H_3$ chooses the same $y_i$ as $\A$ in $H_2$, but they set $x_i = 0$ if $b_i = 1$.  Then choose $y'_N = y_N \bigoplus_{b_i = 1} f_\pi^i(y_i)$.  Then $R'_{N+1} = R'_N \oplus y'_N = R_N \oplus y_N = 0$, so $H_3 = 1$.

Suppose $H_3 = 1$.  Then $R_{N+1} = 0$, so $H_2 = 1$.
\end{proof}



















\end{document}